package 整数;

/**
 * @author: 大怪
 * @email: 962527441@qq.com
 */

/**
 * 题目：
 * 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
 *
 * 实例：
 * 输入: n = 2
 * 输出: [0,1,1]
 * 解释:
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 */
public class 前n个数字二进制中1的个数 {
    class Solution {
        public int[] countBits(int n) {
            int a[] = new int[n+1];
            for (int i = 1; i < a.length; i++) {
                if (i%2 == 1) {
                    a[i] = a[i-1]+1;
                }else {
                    a[i] = a[i/2];
                }
            }
            return a;
        }
    }
}
